#pragma once

#include "../base/types.h"
#include <stdlib.h>
#include <string.h>
#include <string>

OPEN_JLIB_NS

struct IntegerQR;

struct Integer {

  struct Num {
    s32 refs;
    u32 size;
    u32 data[3];
    static u64 __counter;

    inline static Num* allocate (u32 capacity) noexcept {
      auto num = (Num*)malloc((2 + capacity) * sizeof(u32));
      num->refs = 1;
      ++__counter;
      return num;
    }

    inline Num* retain () noexcept {
      refs++;
      return this;
    }

    inline void release () noexcept {
      if (--refs <= 0) {
        free(this);
        --__counter;
      }
    }

    inline void shrink (u32 length) noexcept {
      for (size = length; size && data[size - 1] == 0; --size);
    }

    inline Num (u32 src) noexcept : refs(1), size(1) {
      data[0] = src;
    }
  };

  template<typename _Type>
  inline static void __udiv (_Type& ql, _Type& rh, _Type a) noexcept {
#if __x86_64__
    asm volatile ("DIV %[a]": [q]"+a"(ql), [r]"+d"(rh): [a]"r"(a));
#else
#endif
  }

  template<typename _Type>
  inline static void __swap (_Type& a, _Type& b) noexcept {
#if __x86_64__
    asm volatile ("XCHG %[b], %[a]": [a]"+r"(a), [b]"+r"(b));
#else
    auto t = a;
    a = b;
    b = t;
#endif
  }

  inline static u32 __leading_zeros (u32 a) noexcept {
    u32 d;
#if __x86_64__
    asm volatile ("BSR %[a], %[d]": [d]"=r"(d): [a]"r"(a));
    d = 31 - d;
#elif __aarch64__
    asm volatile ("CLZ %[d], %[a]": [d]"=r"(d): [a]"r"(a));
#else
    if (a == 0)
      return 32;
    d = 1;
    if (a >> 16 == 0) { d += 16; a <<= 16; }
    if (a >> 24 == 0) { d +=  8; a <<=  8; }
    if (a >> 28 == 0) { d +=  4; a <<=  4; }
    if (a >> 30 == 0) { d +=  2; a <<=  2; }
    d -= a >> 31;
#endif
    return d;
  }

  inline static s32 __trailing_zeros (u32 a) noexcept {
    u32 d;
#if __x86_64__
    asm volatile ("BSF %[a], %[d]": [d]"=r"(d): [a]"r"(a));
#else
    if (a == 0)
      return 32;
    d = 1;
    if (a << 16 == 0) { d += 16; a >>= 16; }
    if (a << 24 == 0) { d +=  8; a >>=  8; }
    if (a << 28 == 0) { d +=  4; a >>=  4; }
    if (a << 30 == 0) { d +=  2; a >>=  2; }
    d -= a & 1;
#endif
    return d;
  }

  inline static s32 __msb (u32 a) noexcept {
    s32 d;
#if __x86_64__
    asm volatile ("BSR %[a], %[d]": [d]"=r"(d): [a]"r"(a));
#elif __aarch64__
    asm volatile ("CLZ %[d], %[a]": [d]"=r"(d): [a]"r"(a));
    d = 31 - d;
#else
    if (a == 0)
      return -1;
    d = 1;
    if (a >> 16 == 0) { d += 16; a <<= 16; }
    if (a >> 24 == 0) { d +=  8; a <<=  8; }
    if (a >> 28 == 0) { d +=  4; a <<=  4; }
    if (a >> 30 == 0) { d +=  2; a <<=  2; }
    d -= a >> 31;
#endif
    return d;
  }

  inline static s32 __lsb (u32 a) noexcept {
    s32 d;
#if __x86_64__
    asm volatile ("BSF %[a], %[d]": [d]"=r"(d): [a]"r"(a));
#else
    if (a == 0)
      return -1;
    d = 31;
    if (a << 16 == 0) { d -= 16; a <<= 16; }
    if (a << 8 == 0) { d -=  8; a <<=  8; }
    if (a << 4 == 0) { d -=  4; a <<=  4; }
    if (a << 2 == 0) { d -=  2; a <<=  2; }
    d -= (a << 1) >> 31;
#endif
    return d;
  }

  static void __and (u32* dst, const u32* op1, u32 len1, const u32* op2, u32 len2) noexcept;
  static void __andn (u32* dst, const u32* op1, u32 len1, const u32* op2, u32 len2) noexcept;
  static void __or (u32* dst, const u32* op1, u32 len1, const u32* op2, u32 len2) noexcept;
  static void __orn (u32* dst, const u32* op1, u32 len1, const u32* op2, u32 len2) noexcept;
  static void __xor (u32* dst, const u32* op1, u32 len1, const u32* op2, u32 len2) noexcept;
  static void __xorn (u32* dst, const u32* op1, u32 len1, const u32* op2, u32 len2) noexcept;
  static void __not (u32* dst, const u32* src, u32 len) noexcept;

  static u32 __shl (u32* dst, const u32* src, u32 len, u32 shift) noexcept;
  static u32 __shr (u32* dst, const u32* src, u32 len, u32 shift) noexcept;

  static s32 __cmp (const u32* op1, u32 len1, const u32* op2, u32 len2) noexcept;
  static u32 __add (u32* dst, const u32* op1, u32 len1, u32 op2) noexcept;
  static u32 __add (u32* dst, const u32* op1, u32 len1, const u32* op2, u32 len2) noexcept;
  static s32 __sub (u32* dst, const u32* op1, u32 len1, u32 op2) noexcept;
  static s32 __sub (u32* dst, const u32* op1, u32 len1, const u32* op2, u32 len2) noexcept;
  static u32 __mul (u32* dst, const u32* op1, u32 len1, u32 op2) noexcept;
  static void __mul (u32* dst, const u32* op1, u32 len1, const u32* op2, u32 len2) noexcept;
  static u32 __div (u32* dst, const u32* op1, u32 len1, u32 op2) noexcept;
  static void __div (u32* dst, u32* mod, const u32* op1, u32 len1, const u32* op2, u32 len2) noexcept;

  static u32 __check_digit (const c8* src) noexcept;
  static u32 __check_digit (const c8* src, u32 len) noexcept;
  static s32 __encode_sign (c8 src) noexcept;
  static u32 __encode_digit (const c8* src, u32 len) noexcept;
  static void __decode_digit (std::string& dst, Num* src) noexcept;

  inline static Integer __one (s32 sign) noexcept {
    return {&__One, sign};
  }

  inline Integer () noexcept : _num(nullptr), _sig(0) {
    ++__counter;
  }

  inline Integer (Num* num, s32 sign) noexcept : _num(num), _sig(sign) {
    ++__counter;
    _num->retain();
  }

  inline Integer (Num* num, s32 sign, bool) noexcept : _num(num), _sig(sign) {
    ++__counter;
  }

public:
  Integer (s64 src) noexcept;
  explicit Integer (const c8* src) noexcept;
  Integer (const c8* src, u32 len) noexcept;

  inline Integer (const Integer& other) noexcept : _num(other._num), _sig(other._sig) {
    ++__counter;
    if (_num)
      _num->retain();
  }

  inline Integer& operator= (const Integer& other) noexcept {
    if (other._num)
      other._num->retain();
    if (_num)
      _num->release();
    _num = other._num;
    _sig = other._sig;
    return *this;
  }

  inline operator bool () const noexcept {
    return _sig != 0;
  }

  inline ~Integer () noexcept {
    if (_num)
      _num->release();
    --__counter;
  }

  inline s32 sign () const noexcept {
    return _sig;
  }

  inline bool odd () const noexcept {
    return _num && _num->size ? bool(_num->data[0] & 1) : false;
  }

  inline bool even () const noexcept {
    return _num && _num->size ? !(_num->data[0] & 1) : true;
  }

  std::string str (bool sign = false) const noexcept;

  s32 msb () const noexcept;
  s32 lsb () const noexcept;
  s32 cmp (const Integer& other) const noexcept;

  Integer operator+ (const Integer& other) const noexcept;
  Integer operator- (const Integer& other) const noexcept;
  Integer operator* (const Integer& other) const noexcept;
  Integer operator/ (const Integer& other) const;
  Integer operator% (const Integer& other) const;

  Integer operator- () const noexcept;
  Integer abs () const noexcept;
  Integer pow (u32 exp) const noexcept;

  Integer operator& (const Integer& other) const noexcept;
  Integer operator| (const Integer& other) const noexcept;
  Integer operator^ (const Integer& other) const noexcept;
  Integer operator~ () const noexcept;
  Integer operator<< (u32 shift) const noexcept;
  Integer operator>> (u32 shift) const noexcept;

  bool operator== (const Integer& other) const noexcept;
  bool operator!= (const Integer& other) const noexcept;
  bool operator< (const Integer& other) const noexcept;
  bool operator<= (const Integer& other) const noexcept;
  bool operator> (const Integer& other) const noexcept;
  bool operator>= (const Integer& other) const noexcept;

  static IntegerQR div_mod (const Integer& op1, const Integer& op2);

  inline static Integer positive_one () noexcept {
    return {&__One, 1};
  }

  inline static Integer negative_one () noexcept {
    return {&__One, -1};
  }

public:
  static Num __One;
  static Num __Ten;
  static u64 __counter;
  Num* _num;
  s32 _sig;
};


inline Integer operator"" _Int (const c8* literal) noexcept {
  return Integer{literal};
}

inline Integer operator"" _Int (const c8* literal, uwl length) noexcept {
  return Integer{literal, u32(length)};
}


struct IntegerQR {
  Integer q;
  Integer r;
};

CLOSE_JLIB_NS